//https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();

        vector<int> dpf(n);
        auto dpg = dpf;

        dpf[0] = -prices[0];
        dpg[0] = 0;

        for (int i = 1; i < n; i++)
        {
            dpf[i] = max((dpg[i - 1] - prices[i]), dpf[i - 1]);
            dpg[i] = max(dpg[i - 1], (dpf[i - 1] + prices[i] - fee));
        }

        return max(dpf[n - 1], dpg[n - 1]);

    }
};